Tinker dex 代码修复解析

Tinker dex 代码修复

Dex 代码的修复方案是 classloader 机制。具体原理是将修复后的 dex 文件插入到 dex 数组的最前面。

众所周知，Android 工程的 java 代码会被编译打包放在 dex 文件中。dex 结构图如下:

使用 010Editor 程序可以清晰查看 dex 文件:

dex 的 diff

dex 文件的差分采用了微信自研的 DexDiff 算法。相比 BsDiff 以文件粒度进行差分，DexDiff 算法深度利用Dex的格式来减少差异的大小，粒度更小。

dex 差分的入口是在 DexPatchGenerator 类。

// 构造函数传入了新 dex 文件和老 dex 文件,Dex 的构造函数会将文件解析转换为 Dex 对象
public DexPatchGenerator(File oldDexFile, File newDexFile) throws IOException {
    this(new Dex(oldDexFile), new Dex(newDexFile));
}

executeAndSaveTo 用来生成差分包。它对 dex 各区域的数据分别进行差分:

public void executeAndSaveTo(OutputStream out) throws IOException {
    // Firstly, collect information of items we want to remove additionally
    // in new dex and set them to corresponding diff algorithm implementations.
    Pattern[] classNamePatterns = new Pattern[this.additionalRemovingClassPatternSet.size()];
    int classNamePatternCount = 0;
    for (String regExStr : this.additionalRemovingClassPatternSet) {
        classNamePatterns[classNamePatternCount++] = Pattern.compile(regExStr);
    }

    List<Integer> typeIdOfClassDefsToRemove = new ArrayList<>(classNamePatternCount);
    List<Integer> offsetOfClassDatasToRemove = new ArrayList<>(classNamePatternCount);
    for (ClassDef classDef : this.newDex.classDefs()) {
        String typeName = this.newDex.typeNames().get(classDef.typeIndex);
        for (Pattern pattern : classNamePatterns) {
            if (pattern.matcher(typeName).matches()) {
                typeIdOfClassDefsToRemove.add(classDef.typeIndex);
                offsetOfClassDatasToRemove.add(classDef.classDataOffset);
                break;
            }
        }
    }

    ((ClassDefSectionDiffAlgorithm) this.classDefSectionDiffAlg)
            .setTypeIdOfClassDefsToRemove(typeIdOfClassDefsToRemove);
    ((ClassDataSectionDiffAlgorithm) this.classDataSectionDiffAlg)
            .setOffsetOfClassDatasToRemove(offsetOfClassDatasToRemove);

    // Then, run diff algorithms according to sections' dependencies.

    // Use size calculated by algorithms above or from dex file definition to
    // calculate sections' offset and patched dex size.

    // Calculate header and id sections size, so that we can work out
    // the base offset of typeLists Section.
    int patchedheaderSize = SizeOf.HEADER_ITEM;
    int patchedStringIdsSize = newDex.getTableOfContents().stringIds.size * SizeOf.STRING_ID_ITEM;
    int patchedTypeIdsSize = newDex.getTableOfContents().typeIds.size * SizeOf.TYPE_ID_ITEM;

    // Although simulatePatchOperation can calculate this value, since protoIds section
    // depends on typeLists section, we can't run protoIds Section's simulatePatchOperation
    // method so far. Instead we calculate protoIds section's size using information in newDex
    // directly.
    int patchedProtoIdsSize = newDex.getTableOfContents().protoIds.size * SizeOf.PROTO_ID_ITEM;

    int patchedFieldIdsSize = newDex.getTableOfContents().fieldIds.size * SizeOf.MEMBER_ID_ITEM;
    int patchedMethodIdsSize = newDex.getTableOfContents().methodIds.size * SizeOf.MEMBER_ID_ITEM;
    int patchedClassDefsSize = newDex.getTableOfContents().classDefs.size * SizeOf.CLASS_DEF_ITEM;

    int patchedIdSectionSize =
            patchedStringIdsSize
                    + patchedTypeIdsSize
                    + patchedProtoIdsSize
                    + patchedFieldIdsSize
                    + patchedMethodIdsSize
                    + patchedClassDefsSize;

    this.patchedHeaderOffset = 0;

    // The diff works on each sections obey such procedure:
    //  1. Execute diff algorithms to calculate indices of items we need to add, del and replace.
    //  2. Execute patch algorithm simulation to calculate indices and offsets mappings that is
    //  necessary to next section's diff works.

    // Immediately do the patch simulation so that we can know:
    //  1. Indices and offsets mapping between old dex and patched dex.
    //  2. Indices and offsets mapping between new dex and patched dex.
    // These information will be used to do next diff works.

    //对字符串区域的差分
    this.patchedStringIdsOffset = patchedHeaderOffset + patchedheaderSize;
    if (this.oldDex.getTableOfContents().stringIds.isElementFourByteAligned) {
        this.patchedStringIdsOffset
                = SizeOf.roundToTimesOfFour(this.patchedStringIdsOffset);
    }
    this.stringDataSectionDiffAlg.execute();
    this.patchedStringDataItemsOffset = patchedheaderSize + patchedIdSectionSize;
    if (this.oldDex.getTableOfContents().stringDatas.isElementFourByteAligned) {
        this.patchedStringDataItemsOffset
                = SizeOf.roundToTimesOfFour(this.patchedStringDataItemsOffset);
    }
    this.stringDataSectionDiffAlg.simulatePatchOperation(this.patchedStringDataItemsOffset);

   ......

    this.classDefSectionDiffAlg.execute();
    this.patchedClassDefsOffset = this.patchedMethodIdsOffset + patchedMethodIdsSize;
    if (this.oldDex.getTableOfContents().classDefs.isElementFourByteAligned) {
        this.patchedClassDefsOffset = SizeOf.roundToTimesOfFour(this.patchedClassDefsOffset);
    }

    // Calculate any values we still know nothing about them.
    this.patchedMapListOffset
            = this.patchedEncodedArrayItemsOffset
            + this.encodedArraySectionDiffAlg.getPatchedSectionSize();
    if (this.oldDex.getTableOfContents().mapList.isElementFourByteAligned) {
        this.patchedMapListOffset = SizeOf.roundToTimesOfFour(this.patchedMapListOffset);
    }
    int patchedMapListSize = newDex.getTableOfContents().mapList.byteCount;

    this.patchedDexSize
            = this.patchedMapListOffset
            + patchedMapListSize;

    // Finally, write results to patch file.
    writeResultToStream(out);
}

差分工作是在 DexSectionDiffAlgorithm.java 中完成的，DexSectionDiffAlgorithm 是个抽象类，它的 execute 方法描述了差分的大致骨架,具体的实现是在各个子类完成的。骨架代码如下:

public void execute() {
    this.patchOperationList.clear();

		//收集新老 dex 里的数据项、进行排序操作
    this.adjustedOldIndexedItemsWithOrigOrder = collectSectionItems(this.oldDex, true);
    this.oldItemCount = this.adjustedOldIndexedItemsWithOrigOrder.length;

    AbstractMap.SimpleEntry<Integer, T>[] adjustedOldIndexedItems = new AbstractMap.SimpleEntry[this.oldItemCount];
    System.arraycopy(this.adjustedOldIndexedItemsWithOrigOrder, 0, adjustedOldIndexedItems, 0, this.oldItemCount);
    Arrays.sort(adjustedOldIndexedItems, this.comparatorForItemDiff);

    AbstractMap.SimpleEntry<Integer, T>[] adjustedNewIndexedItems = collectSectionItems(this.newDex, false);
    this.newItemCount = adjustedNewIndexedItems.length;
    Arrays.sort(adjustedNewIndexedItems, this.comparatorForItemDiff);

		//使用两个指针遍历新老元素，将新增元素、删除的元素保存到 patchOperationList
    int oldCursor = 0;
    int newCursor = 0;
    while (oldCursor < this.oldItemCount || newCursor < this.newItemCount) {
        if (oldCursor >= this.oldItemCount) {
            // rest item are all newItem.
            while (newCursor < this.newItemCount) {
                AbstractMap.SimpleEntry<Integer, T> newIndexedItem = adjustedNewIndexedItems[newCursor++];
                this.patchOperationList.add(new PatchOperation<>(PatchOperation.OP_ADD, newIndexedItem.getKey(), newIndexedItem.getValue()));
            }
        } elseu a
        if (newCursor >= newItemCount) {
            // rest item are all oldItem.
            while (oldCursor < oldItemCount) {
                AbstractMap.SimpleEntry<Integer, T> oldIndexedItem = adjustedOldIndexedItems[oldCursor++];
                int deletedIndex = oldIndexedItem.getKey();
                int deletedOffset = getItemOffsetOrIndex(deletedIndex, oldIndexedItem.getValue());
                this.patchOperationList.add(new PatchOperation<T>(PatchOperation.OP_DEL, deletedIndex));
                markDeletedIndexOrOffset(this.oldToPatchedIndexMap, deletedIndex, deletedOffset);
            }
        } else {
            AbstractMap.SimpleEntry<Integer, T> oldIndexedItem = adjustedOldIndexedItems[oldCursor];
            AbstractMap.SimpleEntry<Integer, T> newIndexedItem = adjustedNewIndexedItems[newCursor];
            int cmpRes = oldIndexedItem.getValue().compareTo(newIndexedItem.getValue());
            if (cmpRes < 0) {
                int deletedIndex = oldIndexedItem.getKey();
                int deletedOffset = getItemOffsetOrIndex(deletedIndex, oldIndexedItem.getValue());
                this.patchOperationList.add(new PatchOperation<T>(PatchOperation.OP_DEL, deletedIndex));
                markDeletedIndexOrOffset(this.oldToPatchedIndexMap, deletedIndex, deletedOffset);
                ++oldCursor;
            } else
            if (cmpRes > 0) {
                this.patchOperationList.add(new PatchOperation<>(PatchOperation.OP_ADD, newIndexedItem.getKey(), newIndexedItem.getValue()));
                ++newCursor;
            } else {
                int oldIndex = oldIndexedItem.getKey();
                int newIndex = newIndexedItem.getKey();
                int oldOffset = getItemOffsetOrIndex(oldIndexedItem.getKey(), oldIndexedItem.getValue());
                int newOffset = getItemOffsetOrIndex(newIndexedItem.getKey(), newIndexedItem.getValue());

                if (oldIndex != newIndex) {
                    this.oldIndexToNewIndexMap.put(oldIndex, newIndex);
                }

                if (oldOffset != newOffset) {
                    this.oldOffsetToNewOffsetMap.put(oldOffset, newOffset);
                }

                ++oldCursor;
                ++newCursor;
            }
        }
    }

    // So far all diff works are done. Then we perform some optimize works.
    // detail: {OP_DEL idx} followed by {OP_ADD the_same_idx newItem}
    // will be replaced by {OP_REPLACE idx newItem}
    Collections.sort(this.patchOperationList, comparatorForPatchOperationOpt);

		//针对 index 相同的 OP_DEL 和 OP_ADD 操作，将其转换为 OP_REPLACE
    Iterator<PatchOperation<T>> patchOperationIt = this.patchOperationList.iterator();
    PatchOperation<T> prevPatchOperation = null;
    while (patchOperationIt.hasNext()) {
        PatchOperation<T> patchOperation = patchOperationIt.next();
        if (prevPatchOperation != null
            && prevPatchOperation.op == PatchOperation.OP_DEL
            && patchOperation.op == PatchOperation.OP_ADD
        ) {
            if (prevPatchOperation.index == patchOperation.index) {
                prevPatchOperation.op = PatchOperation.OP_REPLACE;
                prevPatchOperation.newItem = patchOperation.newItem;
                patchOperationIt.remove();
                prevPatchOperation = null;
            } else {
                prevPatchOperation = patchOperation;
            }
        } else {
            prevPatchOperation = patchOperation;
        }
    }

    // Finally we record some information for the final calculations.
    //把增加元素、删除元素、修改元素的操作分别存放到三个集合中
    patchOperationIt = this.patchOperationList.iterator();
    while (patchOperationIt.hasNext()) {
        PatchOperation<T> patchOperation = patchOperationIt.next();
        switch (patchOperation.op) {
            case PatchOperation.OP_DEL: {
                indexToDelOperationMap.put(patchOperation.index, patchOperation);
                break;
            }
            case PatchOperation.OP_ADD: {
                indexToAddOperationMap.put(patchOperation.index, patchOperation);
                break;
            }
            case PatchOperation.OP_REPLACE: {
                indexToReplaceOperationMap.put(patchOperation.index, patchOperation);
                break;
            }
            default: {
                break;
            }
        }
    }
}

最后调用 DexPatchGenerator.java 的 writePatchOperations 方法将 patch 信息写入差分包文件中:

private <T extends Comparable<T>> void writePatchOperations(
        DexDataBuffer buffer, List<PatchOperation<T>> patchOperationList
) {
    List<Integer> delOpIndexList = new ArrayList<>(patchOperationList.size());
    List<Integer> addOpIndexList = new ArrayList<>(patchOperationList.size());
    List<Integer> replaceOpIndexList = new ArrayList<>(patchOperationList.size());
    List<T> newItemList = new ArrayList<>(patchOperationList.size());

    for (PatchOperation<T> patchOperation : patchOperationList) {
        switch (patchOperation.op) {
            case PatchOperation.OP_DEL: {
                delOpIndexList.add(patchOperation.index);
                break;
            }
            case PatchOperation.OP_ADD: {
                addOpIndexList.add(patchOperation.index);
                newItemList.add(patchOperation.newItem);
                break;
            }
            case PatchOperation.OP_REPLACE: {
                replaceOpIndexList.add(patchOperation.index);
                newItemList.add(patchOperation.newItem);
                break;
            }
            default:
                break;
        }
    }

    buffer.writeUleb128(delOpIndexList.size());
    int lastIndex = 0;
    for (Integer index : delOpIndexList) {
        buffer.writeSleb128(index - lastIndex);
        lastIndex = index;
    }

    buffer.writeUleb128(addOpIndexList.size());
    lastIndex = 0;
    for (Integer index : addOpIndexList) {
        buffer.writeSleb128(index - lastIndex);
        lastIndex = index;
    }

    buffer.writeUleb128(replaceOpIndexList.size());
    lastIndex = 0;
    for (Integer index : replaceOpIndexList) {
        buffer.writeSleb128(index - lastIndex);
        lastIndex = index;
    }

    for (T newItem : newItemList) {
        if (newItem instanceof StringData) {
            buffer.writeStringData((StringData) newItem);
        } else
        if (newItem instanceof Integer) {
            // TypeId item.
            buffer.writeInt((Integer) newItem);
        }
        ......
    }
}

以字符串的 diff 过程为例, 假设老 dex 文件中字符串序列为 “c”、”a”、”d”、”e” ，新dex 文件中字符串序列为 “c”、”b”、”e”、”f”

先收集字符串序列，老字符串序列为 {0,”c”},{1,”a”},{2,”d”},{3,”e”},新字符串序列为 {0,”c”},{1,”b”},{2,”e”},{3,”f”}

排序后的序列分别为 {1,”a”},{0,”c”},{2,”d”},{3,”e”} 和 {1,”b”},{0,”c”},{2,”e”},{3,”f”}

使用指针 oldCursor、newCursor 遍历后得到的操作序列为 {OP_DEL,1}、{OP_ADD,1,”b”}、{OP_DEL,2}、{OP_ADD,3,”f”}

对操作序列进行排序和合并后得到序列: {OP_REPLACE,1,”b”}、{OP_DEL,2}、{OP_ADD,3,”f”}

将信息写入 patch 包对 StringData 区域中：

各个区域的差分信息都写入 patch 包后，生成的 patch 包格式如下:

参考链接:

Android 热修复 Tinker 源码分析之DexDiff / DexPatch

tinker-dex-dump

Dalvik Executable format

一篇文章带你搞懂DEX文件的结构

安卓App热补丁动态修复技术介绍